Prototyping a complex digital integrated circuit is complex and cost-intensive. As a design evolves and is debugged, circuit details may change. Should the design be embodied in an application specific integrated circuit (ASIC), the changes in design require mask changes and also affect related processing steps, thus requiring costly process changes. By prototyping the circuit using a PLD such as a field programmable gate array (FPGA), a user may debug and evolve the design without worrying about related process step changes that would be required if an ASIC were used to implement the design.
The configurability of a PLD into a given logical design comes at the cost of larger semiconductor die area (to provide the programmable features) as compared to an ASIC implementation. Thus, PLDs are often used during the prototyping stage but later replaced by ASICs as the design matures and production volumes increase. However, PLDs are increasingly replacing ASICs even in mature, prototyped applications because their re-programmability allows a user to upgrade or change a configuration over time with respect to software upgrades and the like.
The advantages of PLDs such as FPGAs over ASICs have increased as the logical resources have grown ever larger. It is now conventional for a modern FPGA to have the capacity of millions of logic gates. As the size of programmable logic devices increases due to technological advances, place-and-route tools necessary to configure the logical resources of a PLD are facing an ever more severe problem of balancing routability and performance with respect to the maximum achievable frequency of operation (Fmax) for the PLD. A slow design will not be competitive in today's FPGA market.
To configure an FPGA into a desired logic state, a user first maps the logical design into a netlist. A place-and-route software tool then maps the various logic functions within the netlist to logic blocks in the programmable logic device. Each of the numerous logic blocks within an FPGA may be configured by the place-and-route tool to perform a desired logical function. For example, one logic block may be configured to perform a logical AND function, another logic block may be configured to perform a logical NAND function, and so on. The input signals to a given logic block and its output signals are routed on a routing structure that connects the various logic blocks. Thus, a configuration must not only program the logic blocks into the appropriate logical configuration but must also configure the routing structure accordingly so that the various inputs and outputs to the logic blocks are routed appropriately. To configure the routing structure appropriately, switches within the routing structure are configured to connect the various logic blocks so that the input and output signals are driven as necessary.
The potential configuration of an FPGA by a place-and-route tool may be better understood with reference to FIG. 1, which illustrates a conventional FPGA 100. For illustration clarity, FPGA 100 includes just four logic blocks 105. The routing structure coupling input and output signals for these logic blocks is organized into row routing resources 110 and column routing resources 115. Each row and column routing resource includes a plurality of conductors for propagating the input and output signals. At each row and column resource intersection, a switch box 120 includes a plurality of switches for connecting selected row and column conductors. Input and output signals to the FPGA 100 are routed though input/output (I/O) circuits 130 that also connect to row and column routing resources through appropriate switch boxes.
A “place” portion of the place-and-route process for FPGA 100 involves the assignment of selected logical blocks to perform necessary logical functions within the net list. It is conventional for the detailed routing stage to be performed using “simulated annealing” techniques as known in the programmable logic arts. The “route” portion involves the configuration of the switch boxes so that the associated input and output signals for the various logic blocks are routed as demanded by the net list. The routing process is often implemented in stages through an initial global routing stage followed by a detailed routing stage. Global routing assumes that the switch boxes 120 are “fully populated” such that any given row conductor within a row routing resource 110 coupling to a switch box 120 may be connected to any given column conductor within a column routing resource 120 coupling to the same switch box (and vice versa). Because fully-populated switch boxes demand a great deal of semiconductor die space, it is conventional to construct the switch boxes as partially populated such that certain row conductors cannot be coupled through a corresponding switch box to certain column conductors. Such switch box routing restrictions are ignored during global routing. Because the various configured logic blocks must, connect to each other as demanded by the netlist being implemented, the detailed routing stage following the global routing stage determines actual switchbox switch setting to accommodate the required connections.
Because there is a large plurality of logic blocks and a robust routing structure connecting the logic blocks in a modern FPGA, such FPGAs may be configured in many different ways. It may be readily appreciated that if a given logic block requires an output from another logic block, an efficient configuration of the PLD would have these logic blocks immediately adjacent in the FPGA. If they are relatively far apart, the configuration will introduce unnecessary delay. However, the routing resources are typically arranged in rows and columns. Each row and column may accommodate only so many signals. Such constraints will fight the optimal placement of logic blocks in that, from an input/output viewpoint, it may be desirable to place logic blocks within the same row or column but it may not be possible for the routing structure to accommodate such placement.
Thus, it is conventional for a place-and-route tool to use tradeoffs to balance the competing goals for a programmable logic device configuration. In a first cut, the place-and-route tool will use global routing considerations to map the logical design to various logic blocks in the FPGA. Global routing does not assign a given signal to a given wire within a row or column of the routing structure. In other words, each row and column of the routing structure may be considered to form a bus having a width representing the total number of signals that may be accommodated on a given row or column routing resource. During a simulated annealing step after global routing, each of the various input signals and output signals to the logic blocks must be assigned to a particular row or column within the routing resources.
Because a partially-routed design is useless for implementing the required netlists, routability must typically take priority over design speed during the place-and-route process. But such a balanced approach will not achieve the highest possible Fmax. Therefore, there is a need in the art for improved programming tools to increase the maximum frequency of operation (Fmax) for PLDs.